As computers grow faster and faster, computer users are able to use more advanced applications, requiring ever more speed from their computers. One of the most important application areas at present is graphics.
In graphics it is often necessary to filter two dimensional raster images. One type of nonlinear filter that is used to remove "shot" noise, pixel dropout, and other spurious features of single pixel extent while preserving overall image quality is to replace each input pixel with the median of itself and the surrounding input pixel values.
An example of finding the median of nine elements is shown on pages 171-175 in Graphics Gems, edited by Andrew S. Glassner, copyright 1990 by Academic Press, Inc., Harcourt Brace Jovanovich, Publishers, ISBN 0-12-286165-5. Actual code for that algorithm is shown on page 711. Code for an algorithm for computing the median of 25 elements arranged in a 5.times.5 grid is shown on page 712. These algorithms suffer from having to perform too many pairwise sort operations.
A method for determining the median of nine elements is disclosed in U.S. Pat. No. 5,532,948 to Maashiro Kohne, et. al., titled "Rank Order Filter", but this method is not control-flow-free because it compares certain values in the nine elements to decide what operations to perform in order to determine the median value. In contrast, the method disclosed in this patent uses a control-flow-free method for determining the median of M.times.N numbers because the operations to be performed are not dependent on the values of the M.times.N numbers. The advantage of a control-flow-free method is that implementing it on a Single Instruction Multiple Data (SIMD) processor makes more efficient use of processor parallelism than implementing a non control-flow-free method on the same SIMD processor.
A method for completely sorting nine, ten, twelve, and sixteen elements using a control-flow-free algorithm is shown on page 228 of The Art of Computer Programming, Volume 3, by Donald E. Knuth, copyright 1973 by Addison-Wesley Publishing Company, ISBN 0-201-03803-X. Section 5.3.4 of this book discusses other control-flow-free methods for sorting numbers as well. These methods are optimized for the case when a single set of numbers needs to be sorted once. They do not take advantage of opportunities for reducing the number of pairwise sorts which need to be made when multiple sorts of sets of numbers with common elements are to be made.